package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-10
 * Time:20:46
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 力扣面试经典150:207. 课程表
 * 中等
 * 相关标签
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 *     例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 * 示例 1：
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的
 */

/**
 * 1.构建graph
 * 2.填充edges，就是课程之间的前置关系，画一下图很好理解
 * 3.dfs找环，存在环即为不合理的课程
 * 4.优化，将visited[node]置为2表示在之前的循环中已经访问过该节点，且该节点不在环中
 */
public class canFinish {
    public static void main(String[] args) {
        // 存在环路的情况
        int numCourses4 = 4;
        int[][] prerequisites4 = {{1, 0}, {2, 1}, {3, 2}, {0, 3}};
        boolean result4 = canFinish.canFinish(numCourses4, prerequisites4);
        System.out.println("Test Case 4: " + result4); // 预期输出: false
    }
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        //1构建graph
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        //2构建edges
        //找到从 1 开始找到对应下标在prerequisites中的值
        for (int i = 0; i < prerequisites.length; i++) {
            graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        //3找环
        //从 0 开始，开始的下一个是 0 对应的值
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if(findCircle(i,visited,graph)) return false;
        }
        return true;
    }

    //dfs找环
    private static boolean findCircle(int node, int[] visited, List<List<Integer>> graph) {
        if(visited[node] == 1) return true;
        if(visited[node] == 2) return false;
        visited[node] = 1;
        for (Integer pre : graph.get(node)) {
            if(findCircle(pre,visited,graph)) return true;
        }
        visited[node] = 2;
        return false;
    }
}
